// map.cpp
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include "util/standard.hpp"
#include <cstdio>
#include <cstring>
#include "util/mem.hpp"
#include "util/misc.hpp"
#include "util/hash.hpp"

namespace Ripe {

template <class K, class V>
MapIterator<K,V>::MapIterator(Map<K,V>* m)
{
  map = m;
  i = 0;
}

template <class K, class V>
bool MapIterator<K,V>::get(K* k, V* v)
{
  if (i > map->alloc_size) return false;
  
  while (i < map->alloc_size) {
    Bucket<K,V> *bucket = map->data + i;
    i++;
    if (bucket->type == BucketFull) {
      *k = bucket->key;
      *v = bucket->value;
      return true;
    }  
  }
  return false;  
}

template <class K, class V>
Map<K,V>::Map(uint32_t n)
{
  alloc_size = map_prime(2*n);
  data = (Bucket<K,V>*) gc_malloc(sizeof(Bucket<K,V>) * alloc_size);
  for (uint32_t i = 0; i < alloc_size; i++){
    data[i].type = BucketEmpty;
  }
  size = 0;
}

template <class K, class V>
bool Map<K,V>::get(K key, V* value)
{
  assert(data != NULL);
  uint32_t hash_value = map_hash_key<K>(key) % alloc_size;
  for (uint32_t i = 0; i < alloc_size; i++){
    // Quadratic probing
    uint32_t loc = (hash_value + i*i) % alloc_size;

    if (data[loc].type == BucketEmpty) {
      return false;
    } else if (data[loc].type == BucketFull and map_equal_key<K>(data[loc].key,
                key)){
      *value = data[loc].value;
      return true;
    }
  }
  return false;
}

template <class K, class V>
bool Map<K,V>::set(K key, V value)
{
  assert(data != NULL);

  if (size + 1 > alloc_size / 2){
    // Hash table is now more than 50% full. Rehash.
    uint32_t new_size = map_prime(alloc_size + 1);

    // Get new buckets.
    Bucket<K,V>* data_new = (Bucket<K,V>*) gc_malloc(sizeof(Bucket<K,V>) * new_size);
    for (uint32_t i = 0; i < new_size; i++){
      data_new[i].type = BucketEmpty;
    }

    // Hash into the new buckets.
    for (uint32_t i = 0; i < alloc_size; i++){
      if (data[i].type == BucketFull){
        set2(data_new, new_size, data[i].key, data[i].value);
      }
    }
    // Replace the buckets.
    alloc_size = new_size;
    data = data_new;
  }
  bool found = set2(data, alloc_size, key, value);
  if (not found) size++;
  return found;
}

template <class K, class V>
bool Map<K,V>::set2(Bucket<K,V>* buckets, uint32_t n, K key, V value)
{
  uint32_t hash_value = map_hash_key<K>(key) % n;
  uint32_t empty = -1; bool found_empty = false;

  for (uint32_t i = 0; i < n; i++){
    // Quadratic probing
    uint32_t loc = (hash_value + i*i) % n;

    if (buckets[loc].type == BucketLazy) {
      // Find first empty lazy spot.
      if (not found_empty) {
        empty = loc;
        found_empty = true;
      }
    } else if (buckets[loc].type == BucketEmpty) {
      // Found an empty bucket. If we found a lazy spot before, fill it up now.
      if (found_empty) loc = empty;
      buckets[loc].key = key;
      buckets[loc].value = value;
      buckets[loc].type = BucketFull;
      return false;
    } else if (map_equal_key<K>(buckets[loc].key, key)){
      // Found the key, update it.
      buckets[loc].value = value;
      return true;
    }
  }

  if (found_empty){
    buckets[empty].key = key;
    buckets[empty].value = value;
    buckets[empty].type = BucketFull;
    return false;
  }

  // Should never reach this point, report an error.
  assert_never();
  return false;
}

template <class K, class V>
void Map<K,V>::print()
{
  std::printf("[");
  for (uint32_t i = 0; i < alloc_size; i++){
    switch(data[i].type){
      case BucketFull:
        std::printf("*");
        break;
      case BucketEmpty:
        std::printf(" ");
        break;
      case BucketLazy:
        std::printf(".");
        break;
    }
  }
  std::printf("] %d in %d buckets\n", size, alloc_size);
}

template <class T>
static inline uint32_t map_hash_key(T key)
{
  return hash((char*) &key, sizeof(T));
}

template <class T>
static inline bool map_equal_key(T k1, T k2)
{
  return k1 == k2;
}

template <>
static inline uint32_t map_hash_key(char* key)
{
  return hash(key, std::strlen(key));
}

template <>
static inline bool map_equal_key(char* k1, char* k2)
{
  return std::strcmp(k1, k2) == 0;
}

}
